\section{Sorting}
Before we talk about sorting, we need to discuss what the standard requires for types to be comparable—specifically, the \cpp{strict_weak_ordering} required by sorting algorithms.

\index{\cpp{strict_weak_ordering}}
Implementing a \cpp{strict_weak_ordering} for a custom type at minimum requires providing an overload of \cpp{operator<} with the following behaviour:

\begin{itemize}
    \item irreflexive $\neg f(a,a)$
    \item anti-symmetric $f(a,b) \Rightarrow \neg f(b,a)$
    \item transitive $(f(a,b) \wedge f(b,c)) \Rightarrow f(a,c)$
\end{itemize}

A good default for a \cpp{strict_weak_ordering} implementation is lexicographical ordering. Lexicographical ordering is also the ordering provided by standard containers.

Since C++20 introduced the spaceship operator, user-defined types can easily access the default version of lexicographical ordering.

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/7PjY8fc1G}{\ExternalLink}}
\footnotesize Example of three approaches to implementing lexicographical comparison for a custom type.
\tcblower
\cppfile{code_examples/theory/comparable_code.h}
\end{codebox}

The default lexicographical ordering (line 14) works recursively. It starts with the object’s bases first, left-to-right, depth-first and then non-static members in declaration order (processing arrays element by element, left-to-right).

The type returned for the spaceship operator is the common comparison category type for the bases and members, one of:
\begin{itemize}
    \item \cpp{std::strong_ordering}
    \item \cpp{std::weak_ordering}
    \item \cpp{std::partial_ordering}
\end{itemize}
\index{\cpp{std::strong_ordering}}
\index{\cpp{std::weak_ordering}}
\index{\cpp{std::partial_ordering}}

\subsection{\texorpdfstring{\cpp{std::lexicographical_compare}}{\texttt{std::lexicographical\_compare}}}
\index{\cpp{std::lexicographical_compare}}

Lexicographical \texttt{strict\_weak\_ordering} for ranges is exposed through the \newline\texttt{std::lexicographical\_compare} algorithm.

\cppversions{\texttt{lex\dots compare}}{\CC98}{\CC20}{\CC17}{\CC20}

\constraints{(\cpp{input_range}, \cpp{input_range})}{(\cpp{forward_range}, \cpp{forward_range})}{\cpp{operator<}}{\cpp{strict_weak_ordering}}

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/YGW4ET1oa}{\ExternalLink}}
\footnotesize Example of using \cpp{lexicographical_compare} and the built-in less than operator to compare vectors of integers.
\tcblower
\cppfile{code_examples/algorithms/lexicographical_compare_code.h}
\end{codebox}

Because the standard containers already offer a built-in lexicographical comparison, the algorithm mainly finds use for comparing raw C arrays and in cases when we need to specify a custom comparator.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/djs6TGsEs}{\ExternalLink}}
\footnotesize Example of using \cpp{lexicographical_compare} for C-style arrays and customizing the comparator.
\tcblower
\cppfile{code_examples/algorithms/lexicographical_compare_useful_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::lexicographical_compare_three_way}}{\texttt{std::lexicographical\_compare\_three\_way}}}
\index{\cpp{std::lexicographical_compare_three_way}}

The \texttt{std::lexicographical\_compare\_three\_way} is the spaceship operator equivalent to \texttt{std::lexicographical\_compare}. It returns one of:
\begin{itemize}
    \item\texttt{std::strong\_ordering}
    \item \texttt{std::weak\_ordering}
    \item \texttt{std::partial\_ordering}
\end{itemize}

The type depends on the type returned by the elements' spaceship operator.

\cppversions{\texttt{lex\dots three\_way}}{\CC20}{\CC20}{N/A}{N/A}
\constraints{\texttt{(input\_range, input\_range)}}{}{\texttt{operator<=>}}{\texttt{strong\_ordering}, \texttt{weak\_ordering}, \texttt{partial\_ordering}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/vrEqPaEEz}{\ExternalLink}}
\footnotesize Example of using \cpp{std::lexicographical_compare_three_way}.
\tcblower
\cppfile{code_examples/algorithms/lexicographical_compare_three_way_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::sort}}{\texttt{std::sort}}}
\index{\cpp{std::sort}}

The \cpp{std::sort} algorithm is the canonical $O(n\log n)$ sort (typically implemented as intro-sort).

\cppversions{\texttt{sort}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\cpp{random_access_range}}{\cpp{random_access_range}}{\cpp{operator<}}{\cpp{strict_weak_ordering}}

Due to the $O(n\log n)$ complexity guarantee, \cpp{std::sort} only operates on \cpp{random_access} ranges. Notably, \cpp{std::list} offers a method with an approximate $n\log n$ complexity.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/vef61TWj9}{\ExternalLink}}
\footnotesize Basic example of using \cpp{std::sort} and \cpp{std::list::sort}.
\tcblower
\cppfile{code_examples/algorithms/sort_code.h}
\end{codebox}

With C++20, we can take advantage of projections to sort by a method or member:

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/4aGenq9b6}{\ExternalLink}}
\footnotesize Example of using a projection in conjunction with a range algorithm. The algorithm will sort the elements based on the values obtained by invoking the method \cpp{value} on each element.
\tcblower
\cppfile{code_examples/algorithms/sort_projection_code.h}
\end{codebox}

Before C++14, you would have to fully specify the type of the comparator, i.e. \cpp{std::greater<double>{}}. The type erased variant \cpp{std::greater<>{}} relies on type deduction to determine the parameter types. Projections accept an unary invocable, including pointers to members and member functions.

\subsection{\texorpdfstring{\cpp{std::stable_sort}}{\texttt{std::stable\_sort}}}
\index{\cpp{std::stable_sort}}

The \cpp{std::sort} is free to re-arrange equivalent elements, which can be undesirable when re-sorting an already sorted range. The \cpp{std::stable_sort} provides the additional guarantee of preserving the relative order of equal elements.

\cppversions{\texttt{stable\_sort}}{\CC98}{N/A}{\CC17}{\CC20}
\constraints{\cpp{random_access_range}}{}{\cpp{operator<}}{\cpp{strict_weak_ordering}}

If additional memory is available, stable\_sort remains $O(n\log n)$. However, if it fails to allocate, it will degrade to an $O(n\log n\log n)$ algorithm.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/TKx8qP8bK}{\ExternalLink}}
\footnotesize Example of re-sorting a range using \cpp{std::stable_sort}, resulting in a guaranteed order of elements.
\tcblower
\cppfile{code_examples/algorithms/stable_sort_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::is_sorted}}{\texttt{std::is\_sorted}}}
\index{\cpp{std::is_sorted}}

The \cpp{std::is_sorted} algorithm is a linear check returning a boolean denoting whether the ranges elements are in non-descending order.

\cppversions{\texttt{is\_sorted}}{\CC11}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{forward\_range}}{\texttt{forward\_range}}{\cpp{std::less}}{\texttt{strict\_weak\_ordering}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/T3n9bfqdM}{\ExternalLink}}
\footnotesize Example of testing a range using \cpp{std::is_sorted}.
\tcblower
\cppfile{code_examples/algorithms/is_sorted_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::is_sorted_until}}{\texttt{std::is\_sorted\_until}}}
\index{\cpp{std::is_sorted_until}}

The \cpp{std::is_sorted_until} algorithm returns the first out-of-order element in the given range, thus denoting a sorted sub-range.

\cppversions{\texttt{is\_sorted\_until}}{\CC11}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{forward\_range}}{\texttt{forward\_range}}{\texttt{std::less}}{\texttt{strict\_weak\_ordering}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/1dvboE6b1}{\ExternalLink}}
\footnotesize Example of testing a range using \cpp{std::is_sorted_until}.
\tcblower
\cppfile{code_examples/algorithms/is_sorted_until_code.h}
\end{codebox}

Note that because of the behaviour of \cpp{std::is_sorted_until}, the following is always true:\\
\begin{small}\cpp{std::is_sorted(r.begin(), std::is_sorted_until(r.begin(), r.end()))}\end{small}

\subsection{\texorpdfstring{\cpp{std::partial_sort}}{\texttt{std::partial\_sort}}}
\index{\cpp{std::partial_sort}}

The \cpp{std::partial_sort} algorithm reorders the range's elements such that the leading sub-range is in the same order it would when fully sorted. However, the algorithm leaves the rest of the range in an unspecified order.

\cppversions{\texttt{partial\_sort}}{\CC98}{\CC20}{\CC17}{\CC20}

\constraints{\cpp{(random_access_range, random_access_iterator)}}{\cpp{(random_access_range, random_access_iterator)}}{\cpp{operator<}}{\texttt{strict\_weak\_ordering}}

The benefit of using a partial sort is faster runtime — approximately $O(n*logk)$, where k is the number of elements sorted.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/j6xjM4GnT}{\ExternalLink}}
\footnotesize Example of using \cpp{std::partial_sort} to sort the first three elements of a range.
\tcblower
\cppfile{code_examples/algorithms/partial_sort_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::partial_sort_copy}}{\texttt{std::partial\_sort\_copy}}}
\index{\cpp{std::partial_sort_copy}}

The \cpp{std::partial_sort_copy} algorithm has the same behaviour as \linebreak\cpp{std::partial_sort}; however, it does not operate inline. Instead, the algorithm writes the results to a second range.

\cppversions{\texttt{partial\_sort\_copy}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\cpp{input_range -> random_access_range}}{\cpp{forward_range -> random_access_range}}{\cpp{operator<}}{\texttt{strict\_weak\_ordering}}

The consequence of writing output to a second range is that the source range does not have to be mutable nor provide random access.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/vjKc5nY31}{\ExternalLink}}
\footnotesize Example of using \cpp{std::partial_sort_copy} to iterate over ten integers read from standard input and storing the top three values in sorted order.
\tcblower
\cppfile{code_examples/algorithms/partial_sort_copy_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{qsort}}{\texttt{qsort}} - C standard library}
\index{\cpp{qsort}}

Because the C standard library is part of the C++ standard library, we also have access to \cpp{qsort}.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/Y4E63aThP}{\ExternalLink}}
\footnotesize Example of using \cpp{qsort} to sort an array of integers.
\tcblower
\cppfile{code_examples/algorithms/qsort_code.h}
\end{codebox}

I would strongly recommend avoiding \cpp{qsort}, as \cpp{std::sort} and \cpp{std::ranges::sort} should be a better choice in every situation. Moreover, \cpp{qsort} is only valid for trivially copyable types, and those will correctly optimize to \cpp{memcpy} / \cpp{memmove} operations even when using \cpp{std::sort}.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/nT9GPh8Tq}{\ExternalLink}}
\footnotesize Example of using \cpp{std::sort} to achieve the same result as in the previous example.
\tcblower
\cppfile{code_examples/algorithms/qsort_not_code.h}
\end{codebox}